package Algorithm.search.swordOffer;

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字 https://leetcode.cn/problems/que-shi-de-shu-zi-lcof
 * 题目简述：一个长度为n-1的升序数组中包含了0至n-1中某个数除外的n-1个数，找出这个缺失的数
 */
public class MissingNumber {

    public static void main(String[] args) {
        new MissingNumber().missingNumber(new int[]{0,1,3});
    }

    /**
     * 思路：二分查找。循环不变量[0, low)为从0到low按序递增的区间，(high, n-1]为从high+1到n按序递增的区间
     *  检查mid然后更新区间。当low越过high时，按照区间定义low索引就是缺失的数字
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;
        //定义区间[0, low)和(high, n-1]
        int low = 0, high = n-1;
        while (low <= high) {
            int mid = (low + high) / 2;
            //nums[mid]就等于mid，说明从0到mid是按序递增的，更新low
            if (nums[mid] == mid) low = mid + 1;
            //nums[mid]大于mid，则缺失的数字必在[low,mid)间，从mid到n-1是按序递增的，更新high
            else high = mid - 1;
        }
        return low;
    }
}
